package main

/**
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？
*/

/**
方法一:递归
*/
func preorderTraversal(root *TreeNode) (nums []int) {
	preRec(root, &nums)
	return
}

func preRec(root *TreeNode, nums *[]int) {
	if root == nil {
		return
	}
	*nums = append(*nums, root.Val)
	preRec(root.Left, nums)
	preRec(root.Right, nums)
}

/**
方法二:栈迭代
*/
func preorderTraversal2(root *TreeNode) (nums []int) {
	if root == nil {
		return
	}
	treeStack := make([]*TreeNode, 0) //栈右进右出
	treeStack = append(treeStack, root)
	for len(treeStack) > 0 {
		node := treeStack[len(treeStack)-1]      //出栈操作
		treeStack = treeStack[:len(treeStack)-1] //出栈操作
		nums = append(nums, node.Val)
		if node.Right != nil {
			treeStack = append(treeStack, node.Right)
		}
		if node.Left != nil {
			treeStack = append(treeStack, node.Left)
		}
	}
	return
}
